/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package grafox.Algorithms;
import grafox.Domain.*;
import java.util.Hashtable;

/**
 * Algoritmo de Bellman Ford
 *
 */

public class BellmanFord {

        private final GrafoX grafo;
        private final VerticeX origem;

        private Hashtable<VerticeX,Double> pesos;
        private Hashtable<VerticeX,VerticeX> pred;
        private Hashtable<VerticeX,Cor> cores;
       

        public BellmanFord(final GrafoX grafo, VerticeX origem) {
                this.grafo = grafo;
                this.origem = origem;
                this.pesos = new Hashtable<>();
                this.pred = new Hashtable<>();
                computar();
        }
       
       
        /**
         * Efetua o relaxamento.
         *
         * Verifica se o peso do vertice origem somado com o peso da aresta
         * que ligam (u,v) e' menor do que menor do que o peso do vertice destino.
         *
         * @param aresta
         * @return
         */
        private boolean relaxamento(ArestaX aresta) {
                ArestaXPonderada p = (ArestaXPonderada)aresta;
                VerticeX origem = p.getOrigem();
                VerticeX destino = p.getDestino();
                double pesoAresta = pesos.get(origem) + p.getPeso();
                if (pesoAresta < pesos.get(destino)) {
                    pesos.put(destino, pesoAresta);
                    pred.put(destino, origem);
                    return true;
                }
                return false;
        }
       
        /**
         * Executa o algoritmo.
         *
         * Executa o relaxamento V-1 vezes, ou seja, a cada V-1 iteracoes
         * atualiza os pesos e os pais dos vertices.
         */
        private void computar() {
                ArestaXPonderada aresta;
                for(VerticeX x : grafo.getVertices())
                    cores.put(x, Cor.Branco);
                for(VerticeX x : grafo.getVertices())
                {
                    cores.put(x, Cor.Cinza);
                    for(VerticeX x2 : grafo.getVertices())
                    {
                        if(cores.get(x2) == Cor.Branco)
                        {
                            for(ArestaX ar : x.getArestasAdj())
                                relaxamento(ar);
                        }
                    }
                    cores.put(x, Cor.Preto);
                }
        }
       
        /**
         * Verifica se tem ciclos negativos.
         *
         * Percorre a matriz de adj., verifica se o peso do vertice de origem (u)
         * somado com o peso da aresta (u,v) e' menor que o peso do vertice de destino
         *
         * @return
         */
        public boolean temCiclosNegativos() {
                Integer[][] matriz = grafo.getMatrizDeAdjacencia();

                for (int i = 0; i < grafo.getNumeroDeVertices(); i++) {
                        for (int j = 0; j < grafo.getNumeroDeVertices(); j++) {
                                Aresta aresta = new Aresta(i, j, matriz[i][j]);

                                if (pesos[aresta.origem()] + aresta.valor() < pesos[aresta.destino()]) {
                                        return true;
                                }
                        }
                }

                return false;
        }

        public void imprimePesosDosVertices() {
                for (int i = 0; i < pesos.length; i++) {
                        System.out.println("Peso do vertice:" + i + ":" + pesos[i]);
                }
        }
       
        public void imprimePaiDosVertices() {
                for (int i = 0; i < pesos.length; i++) {
                        System.out.println("Pai de " + i + ": " + pred[i]);
                }
        }
        
        public double peso(VerticeX vertice){
            return pesos.get(vertice);
        }

}